import java.util.Scanner;

public class BinarySearch {
   /* 二分查找算法：适用于有序数列，找出中间数，把数列分成两部分，比较中间数和关键字，如果相等，查找成功，如果中间的数小，则在
    右边去找，反之去左边找；重复上面的过程，直到找到为止。
    假设数组是有序的*/
    public static int search(int[]a,int max,int key){
        /*如果a为升序数组，min为最小的数，max为最大的数，key为要找查的数字*/
        if (a==null||max==0){return 0;}
        int min=0;
        if (a[0]<=a[max]){
         while (min<=max) {
            int median=(min+max)/2;//中间数
            if (a[median]==key){return median;}
            if (a[median] < key) {
               min=median+1;
            }
           else  {
               max=median-1;
            }
         }
        }
         /*如果a为降序数组，min为最大的数，max为最小的数，key为要找查的数字*/
        else {
            while (min>=max){
                int median=(min+max)/2;
                if (a[median]==key){return median;}
                if (a[median] >key) {
                    min=median+1;
                }
                else  {
                    max=median-1;
                }
            }
        }
        return -1;

    }
    public static void main(String[]args){
      /*1.用户输入一个数确定数组的长度
      * 2.给随机数排序
      * 3.输入一个已有的数字，程序自动找出这个数所在的位置*/
      Scanner scanner=new Scanner(System.in);
        System.out.println("请输入一个数确定数组的长度：");
      int length=scanner.nextInt();
      int[] a=new int[length];
      for (int i=0;i<a.length;i++){
          a[i]=(int)(100*Math.random());
      }
      /*打印*/
              PrintArray.printArray(a);
              System.out.println("排序：");
              QuickSort quickSort=new QuickSort();
              quickSort.quickSort(a,0,(a.length-1));
              //打印排序后的数组
        for (int i = 0; i< a.length; i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
        //输入要找查的数
        System.out.println("请输入要找查的数");
        int key=scanner.nextInt();
        scanner.close();
        int c=search(a,(a.length-1),key);
        //输出结果
        if (c==-1){
            System.out.println("结果：");
            System.out.println("数组里没有您要找的数");
        }
        else if (c==0){
            System.out.println("结果：");
            System.out.println("数组为空或者没有数");
        }
        else {
            System.out.println("结果：");
            System.out.println("第"+(c+1)+"个是您要找查的数:");
        }

    }
}
